package leetcode_1_200;

import node.TreeNode;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;

public class LeeCode_107 {
    public static void main(String[] args) {
        System.out.println(levelOrderBottom(new TreeNode(3, new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7)))));
        System.out.println(levelOrderBottom(new TreeNode(1)));
        System.out.println(levelOrderBottom(null));
    }

    private static List<List<Integer>> levelOrderBottom(TreeNode root) {
        int depth = getDepth(root, 0);
        List<List<Integer>> ans = new ArrayList<>(depth);
        for (int i = 0; i < depth; i++)
            ans.add(new ArrayList<>());
        f(ans, root, 0, depth);
        return ans;
    }

    private static int getDepth(TreeNode node, int depth){
        if (node == null)
            return depth;
        return Math.max(getDepth(node.left, depth + 1), getDepth(node.right, depth + 1));
    }

    private static void f(List<List<Integer>> ans, TreeNode node, int depth, int max) {
        if (node == null)
            return;
        while (ans.size() - 1 < depth) {
            ans.add(new ArrayList<>());
        }
        f(ans, node.left, depth + 1, max);
        ans.get(max - depth - 1).add(node.val);
        f(ans, node.right, depth + 1, max);
    }
}
